﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GKS.DataTypes.Trees {
    public enum Direction { Left, Right };

    public class BinaryTreeNode<K, V> /*: ICollection<KeyValuePair<K, V>>*/ where K : IComparable<K>, new() {
        #region parameters
        public KeyValuePair<K, V> Element { get; set; }
        public BinaryTreeNode<K, V> Parent { get; set; }
        public BinaryTreeNode<K, V> LeftChild { get; set; }
        public BinaryTreeNode<K, V> RightChild { get; set; }
        public int Depth { get; private set; }
        public int Level { get; private set; }
        public int Count { get; private set; }
        #endregion

        #region constructors
        public BinaryTreeNode(K key, V val) 
            : this(key, val, null) { }
        
        public BinaryTreeNode(KeyValuePair<K, V> element) 
            : this(element, null) { }
        
        public BinaryTreeNode(K key, V val, BinaryTreeNode<K, V> parent) 
            : this(key, val, null, null, parent) { }
        
        public BinaryTreeNode(KeyValuePair<K, V> element, BinaryTreeNode<K, V> parent) 
            : this(element, null, null, parent) { }
        
        public BinaryTreeNode(K key, V val, BinaryTreeNode<K, V> left, BinaryTreeNode<K, V> right, BinaryTreeNode<K, V> parent) 
            : this(new KeyValuePair<K, V>(key, val), left, right, parent) { }
        
        public BinaryTreeNode(KeyValuePair<K, V> element, BinaryTreeNode<K, V> left, BinaryTreeNode<K, V> right, BinaryTreeNode<K, V> parent) {
            Element = element;
            LeftChild = left;
            RightChild = right;
            Parent = parent;
        }
        #endregion

        #region public methods
        #region add new element
        public void Add(K key, V val, Direction[] path) {
            Add(new KeyValuePair<K, V>(key, val), path);
        }

        public void Add(KeyValuePair<K, V> element, Direction[] path) {
            Add(new BinaryTreeNode<K, V>(element), path);
        }

        public void Add(BinaryTreeNode<K, V> newNode, Direction[] path) {
            BinaryTreeNode<K, V> node = this;

            foreach (Direction d in path) {
                if (node.Element.Key.CompareTo(newNode.Element.Key) != 0) {
                    if (d == Direction.Left) {      // we must go left
                        if (node.LeftChild == null) {
                            node.LeftChild = newNode;
                            newNode.Parent = node;
                            break;
                        } else {
                            node = node.LeftChild;
                        }
                    } else {        // we must go right
                        if (node.RightChild == null) {
                            node.RightChild = newNode;
                            newNode.Parent = node;
                            break;
                        } else {
                            node = node.RightChild;
                        }
                    }
                } else {            // we found an element with the same key. replacing the element
                    node.Element = newNode.Element;
                }
            }
        }
        #endregion

        #region search for element
        public BinaryTreeNode<K, V> Search(K key, out BinaryTreeNode<K, V>[] path) {
            List<BinaryTreeNode<K, V>> pathToNode = new List<BinaryTreeNode<K, V>>();
            List<BinaryTreeNode<K, V>> nodes = new List<BinaryTreeNode<K, V>>();
            BinaryTreeNode<K, V> result = null, currentNode;
            int comparison, currentNodeIndex = 0;

            nodes.Add(this);

            do {
                currentNode = nodes.ElementAt(currentNodeIndex);
                comparison = currentNode.Element.Key.CompareTo(key);

                if (comparison == 0) {
                    result = currentNode;
                } else {
                    if (currentNode.LeftChild != null) {
                        nodes.Add(currentNode.LeftChild);
                    }

                    if (currentNode.RightChild != null) {
                        nodes.Add(currentNode.RightChild);
                    }

                    currentNodeIndex++;
                }
            } while (comparison != 0 || currentNodeIndex < nodes.Count);

            if (comparison == 0) {      // means that we have found the node with the given key
                pathToNode.Add(currentNode);        // add the node containing the wanted key

                while (currentNode.Parent != null) {
                    currentNode = currentNode.Parent;
                    pathToNode.Add(currentNode);
                }
            }

            path = pathToNode.ToArray(); 

            return result;
        }
        #endregion

        #region remove from subtree

        #endregion

        #region visits
        public BinaryTreeNode<K, V>[] PreOrderVisit() {
            List<BinaryTreeNode<K, V>> nodesList = new List<BinaryTreeNode<K, V>>();

            this.PreOrderVisit(ref nodesList);

            return nodesList.ToArray();
        }

        public BinaryTreeNode<K, V>[] InOrderVisit() {
            List<BinaryTreeNode<K, V>> nodesList = new List<BinaryTreeNode<K, V>>();
            
            this.InOrderVisit(ref nodesList);

            return nodesList.ToArray();
        }

        public BinaryTreeNode<K, V>[] PostOrderVisit() {
            List<BinaryTreeNode<K, V>> nodesList = new List<BinaryTreeNode<K, V>>();

            this.PostOrderVisit(ref nodesList);

            return nodesList.ToArray();
        }

        public BinaryTreeNode<K, V>[] InBreadthVisit() {
            List<BinaryTreeNode<K, V>> nodesList = new List<BinaryTreeNode<K, V>>();

            nodesList.Add(this);

            for (int i = 0; i < nodesList.Count; i++) {
                if (nodesList.ElementAt(i).LeftChild != null) {
                    nodesList.Add(nodesList.ElementAt(i).LeftChild);
                }

                if (nodesList.ElementAt(i).RightChild != null) {
                    nodesList.Add(nodesList.ElementAt(i).RightChild);
                }
            }

            return nodesList.ToArray();
        }
        #endregion
        #endregion

        #region private methods
        private void PreOrderVisit(ref List<BinaryTreeNode<K, V>> nodesList) {
            nodesList.Add(this);
            
            if (LeftChild != null) {
                LeftChild.InOrderVisit(ref nodesList);
            }

            if (RightChild != null) {
                RightChild.InOrderVisit(ref nodesList);
            }
        }

        private void InOrderVisit(ref List<BinaryTreeNode<K, V>> nodesList) {
            if (LeftChild != null) {
                LeftChild.InOrderVisit(ref nodesList);
            }

            nodesList.Add(this);

            if (RightChild != null) {
                RightChild.InOrderVisit(ref nodesList);
            }
        }

        private void PostOrderVisit(ref List<BinaryTreeNode<K, V>> nodesList) {
            if (LeftChild != null) {
                LeftChild.InOrderVisit(ref nodesList);
            }

            if (RightChild != null) {
                RightChild.InOrderVisit(ref nodesList);
            }

            nodesList.Add(this);
        }
        #endregion
    }
}
